//
//  Problem1300.swift
//  TestProject
//
//  Created by 武侠 on 2021/6/1.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1300. 转变数组后最接近目标值的数组和
 给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。
 如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。
 请注意，答案不一定是 arr 中的数字。

 示例 1：
     输入：arr = [4,9,3], target = 10
     输出：3
     解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。
 示例 2：
     输入：arr = [2,3,5], target = 10
     输出：5
 示例 3：
     输入：arr = [60864,25176,27249,21296,20204], target = 56803
     输出：11361
 提示：
     1 <= arr.length <= 10^4
     1 <= arr[i], target <= 10^5
 */
@objcMembers class Problem1300: NSObject {
    func solution() {
        print(findBestValue([4,9,3], 10))
        print(findBestValue([2,3,5], 10))
        print(findBestValue([60864,25176,27249,21296,20204], 56803))
    }
    
    /*
     标准的二分法 最小值和最大值 求解
     最小值：0，最大值：target
     
     */
    func findBestValue(_ arr: [Int], _ target: Int) -> Int {
        var l = 0, r = target
        var mid = 0, sum = 0
        var minValue = Int.max
        var minMid = Int.max
        while l <= r {
            mid = l + (r - l) >> 1
            
            sum = 0
            for n in arr {
                sum += (n < mid ? n : mid)
            }
            
            // 3 3 4 9 1
            print(l, mid, r, sum, minValue, abs(sum - target))
            if minValue >= abs(sum - target) {  // 满足条件
                minMid =  mid
                if sum > target {
                    r = mid - 1
                } else {
                    l = mid
                }
                minValue = abs(sum - target)
            } else {    // 离target太远了
                if sum > target {
                    r = mid - 1
                } else {
                    l = mid + 1
                }
            }
        }
        return minMid
    }
}
